Typical computer games and other multimedia programs are frequently distributed on removable optical storage media such as CD-ROMs (compact disc-read only memory) and DVDs. CD-ROMs are currently the most common media used for program distribution. DVDs, commonly referred to as digital video discs or digital versatile discs, use a high density optical disc format that has been in development for the past several years. DVD was introduced in Japan and Korea in late 1996, and is expected to be available in the US and other markets in 1997. There are several variations of the DVD format. DVD-Video is a format designed to deliver linear motion picture content. DVD-Audio is a format designed for audio. The term DVD-ROM is used to reference an optical storage medium that is formatted in accordance with the DVD standard.
Games and other programs such as these often use continuous data streams that are stored on the optical storage media for rendering during program execution. Such continuous data streams include video and audio streams. Digital video and audio streams are usually stored in a compressed and encoded format such as industry standards consisting of MPEG-2 Video, MPEG-2 Audio, and other MPEG-2 systems. MPEG stands for the Moving Picture Experts Group, which is a group that coordinates the definition of these standards.
Commonly used optical digital media typically have data stored in continuous spiral tracks. Continuous data can then be read in its proper order at high speeds by reading sequentially along the spiral of the media.
Many multimedia programs and games use a number of media clips that are tied together into a cohesive story under program control or according to user actions. This requires that a program or game be able to instantly switch from one continuous clip to another in response to user input, without any discernible rendering discontinuity or gap between clips. Such gaps are referred to as "seams." A continuous branch, without discontinuities, is referred to as a "seamless" jump or branch. As a specific example, a video game utilizes audio and video clips while allowing users to influence the particular sequence of rendered video clips. In some games, for instance, a user can manipulate a mouse or a joystick to change story lines and influence game outcomes. As the user makes choices, the game responds so that the audio and video appear to flow seamlessly. In many cases, the user at some point will have several different alternatives, and the game must react immediately to whichever of the alternatives is actually chosen by the user.
As used here, the term "clip" refers to a segment of data that is intended to be read and rendered as a stream and that is stored on a storage medium in such a way that it can be read from the storage medium at a rate that is at least as fast as the normal rate at which the data is intended to be rendered. In most cases, an individual media clip will be laid out contiguously along a spiral of a CD-ROM or DVD.
In addition to branching seamlessly to another clip, a program sometimes must access extraneous data files while playing a single media clip. For example, a game might need a data file containing a digitized sound effect of short duration (such as a "beep" to signal an error), which is to be rendered simultaneously with the primary audio and video. When the file must be obtained from the same CD-ROM or DVD, this is referred to as intervening file access.
When using storage media such as CD-ROMs and DVDs, seamless jumps between media clips are difficult to achieve. This is because of the relatively high latency these devices exhibit when switching between different physical locations on the media. The time required to access a different DVD location can be nearly 1/3 of a second. To preserve visual and audio continuity, something needs to be rendered during this time, even though new data is not available.
Existing solutions to this problem primarily involve some type of pre-loading. One solution, for example, requires caching the initial segments, referred to as bridge data, of all media clips that might potentially be the target of a seamless branch. When a branch is taken, the cached data is rendered while accessing the appropriate location on the storage medium. This approach is useful both for intervening file access and for branching from one media clip to another. However, this approach requires significant amounts of low-latency memory to store the bridge data for all available media clips. This is wasteful and expensive, and in some cases is simply not a possibility (such as in a consumer device with no hard disk). Furthermore, new video standards such as MPEG2 require high bandwidths and thus greatly increase the amount of low-latency memory that would be required to implement a pre-loading scheme such as described above.
Some solutions take advantage of storage device characteristics to provide seamless branching. For example, DVD-Video uses data interleaving for multiple angle viewing. Video clips from different camera angles are laid out in an interleaved manner. Angle of view can be changed seamlessly since the video clips corresponding to different camera angles can be delivered simultaneously. This technique has the advantage of requiring no caching beyond internal read-ahead buffering, but is very limited in scope. It cannot be used for general-purpose seamless branching such as used in games or other similar multimedia titles. In addition, some DVD-Video systems utilize a read-ahead buffer to store bridge data. This technique relies on the ability to read data faster than it can be consumed. While this approach is practical in some situations, it imposes limitations on the physical layout of clips. Also, there are many situations, such as where there are a plurality of available branches at a given time, where this approach simply will not work.
Some applications utilize more than one high-latency storage medium for rendering continuous media content, such as two CD-ROMs. However, this is an expensive solution, and requires equipment (two drives) that most users do not have.